package com.leecode.answer;

public class Test {
    public static void main(String[] args) {
        Test test = new Test();
        int brr[][] = new int[][]{new int[]{}
        };
        // [[4],[],[4],[4],[0,2,3]]
        System.out.println(test.isBipartite(brr));
    }
    public boolean isBipartite(int[][] graph) {
        int m = graph.length;
        int[] dp = new int[m];
        for(int i = 0; i < m; i++){
            if(dp[i] == 0){
                dp[i] = 1;
                helper(2, i, dp, graph);
                if(!ans){
                    return false;
                }
            }
        }
        return true;
    }

    boolean ans = true;

    private void helper(int color, int row, int[] dp, int[][] graph){
        for(int j = 0; j < graph[row].length; j++){
            int next = graph[row][j];
            if(dp[next] == 0){
                dp[next] = color;
                helper((color % 2) + 1, next, dp, graph);
                if(!ans){
                    break;
                }
            } else if (dp[next] != color) {
                ans = false;
                break;
            }
        }
    }

}
